Optimal sorting algorithm with modified cost... [closed]

Posted by David on Stack Overflow See other posts from Stack Overflow or by David
Published on 2011-01-14T03:13:19Z Indexed on 2011/01/14 21:53 UTC
Read the original article Hit count: 246

Filed under:
|
|
|

The numbers are in a list that is not sorted and supports only one type of operation. The operation is defined as follows: Given a position i and a position j the operation moves the number at position i to position j without altering the relative order of the other numbers. If i > j, the positions of the numbers between positions j and i - 1 increment by 1, otherwise if i < j the positions of the numbers between positions i+1 and j decreases by 1. This operation requires i steps to find a number to move and j steps to locate the position to which you want to move it. Then the number of steps required to move a number of position i to position j is i+j. Design an algorithm that given a list of numbers, determine the optimal(in terms of cost) sequence of moves to rearrange the sequence.

© Stack Overflow or respective owner

Related posts about algorithm

Related posts about homework